package com.kehao.newcoder;

import java.util.LinkedList;
import java.util.Queue;

public class NC60Solution {

    private class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

        public TreeNode() {
        }
    }

    public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean[] result = new boolean[2];
        result[0] = judgeSearchTree(root,0,1000000);
        result[1] = judgeFullTree(root);
        return result;
    }

    private boolean judgeFullTree(TreeNode root) {
        if(root==null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        int status = 2;
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode remove = queue.remove();
            if(status==2){
                if(remove.left!=null){
                    queue.add(remove.left);
                    if(remove.right!=null){
                        queue.add(remove.right);
                    }else {
                        status = 1;
                    }
                }else if(remove.right==null){
                    status = 0;
                }else {
                    return false;
                }
            }else {
                return remove.left == null && remove.right == null;
            }
        }
        return true;
    }

    private boolean judgeSearchTree(TreeNode root, int min, int max) {
        if(root==null){
            return true;
        }
        if(min> root.val||max< root.val) return false;
        boolean leftResult = true;
        boolean rightResult = true;
        if(root.left!=null){
            leftResult = root.left.val<= root.val;
            leftResult = leftResult&&judgeSearchTree(root.left, min, root.val);
        }
        if(!leftResult){
            return false;
        }
        if(root.right!=null){
            rightResult = root.right.val >= root.val;
            rightResult = rightResult&&judgeSearchTree(root.right, root.val, max);
        }
        if(!rightResult){
            return false;
        }
        return true;
    }
}
